﻿#pragma once
#include "stdafx.h"

/*
合并两个有序链表  简单
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

 

 示例：

 输入：1->2->4, 1->3->4
 输出：1->1->2->3->4->4

 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 解题思路：这个题目比较简单了，并归方式，在数据结构链表的第一章节的时候，
 就有这个功能，判单两个链表第一个是不是为空，不的话，比较大小，开始赋值，小的向后移动，
 一直到最后有一个没有的，把剩下的给复制过去就可以了。
*/

struct ListNode {
	int val;
	ListNode *next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode *next) : val(x), next(next) {}
};

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
{

	ListNode * head = new ListNode(-1);
	ListNode * curNode = head;
	while (l1 && l2)
	{
		if (l1->val < l2->val)
		{
			curNode->next = l1;
			l1= l1->next;
		}
		else
		{
			curNode->next = l2;
			l2 = l2->next;
		}
		curNode = curNode->next;
	}

	curNode->next = l1 == nullptr ? l2 : l1;

	return head->next;
}
